/**
 * 
 */
package edu.umd.clip.lm.util;

import java.util.Arrays;
import java.util.Random;


/**
 * @author Denis Filimonov <den@cs.umd.edu>
 *
 */
public class Sampler {
	private double accumulatedProbabilities[];
	private long vocabulary[];
	private final Random rnd;
	
	public Sampler(CountDistribution dist) {
		this.rnd = new Random();
		this.accumulatedProbabilities = new double[dist.getCounts().size()];
		this.vocabulary = new long[dist.getCounts().size()];
		
		double revCounts = 1.0 / dist.getTotalCount();
		int pos = 0;
		long accCount = 0;
		for(Long2IntMap.Iterator it = dist.getCounts().iterator(); it.hasNext(); ) {
			Long2IntMap.Entry e = it.next();
			long word = e.getKey();
			int count = e.getValue();
			vocabulary[pos] = word;
			accCount += count;
			accumulatedProbabilities[pos] = accCount * revCounts;
			++pos;
		}
	}
	
	public long getSample() {
		double prob = rnd.nextDouble();
		int pos = Arrays.binarySearch(accumulatedProbabilities, prob);
		if (pos < 0) {
			pos = -pos - 1;
			if (pos == accumulatedProbabilities.length) {
				// hypothetically possible due to fp rounding
				pos = accumulatedProbabilities.length - 1;
			}
		}
		return vocabulary[pos];
	}
}
